In DSSS communication systems, PN generators are commonly used to spread or despread the information within the transmitted signal since the information signal bandwidth is much narrower than the spread signal. Such signal bandwidth compression and decompression is useful because of limited availability of transmission signals over finite frequency bands. However, the demand for information and the ability to transmit that information is increasing due to the expanding prevalence of cellular telephones and the like. Likewise, there are a limited number of bandwidths which are available for cellular telephone communications. It is therefore beneficial to transmit as much data or information as possible.
In digital cellular telephones or similar applications, the transmitted DSSS signals received by the cellular telephone or receiver is despread. One function of the PN generator within the cellular telephone is to provide a local PN code sequence for the despread process of the transmitted bit stream or data sequence of the transmitted signal. With signals transmitted from more than one base station to the particular telephone handset or receiver unit, the PN generator correlates such received signals so the cellular telephone receiver unit can demodulate the proper received signal. In a typical CDMA system, i-phase data and q-phase data are used to spread the information to be transmitted. In certain CDMA cellular systems, an i-phase pseudorandom sequence is generated in accordance with the polynomial of Equation (1),p(x)=x15+x13+x9+x8+x7+x5+1  (1).
The implementation of Equation (1) can be accomplished by the Linear Sequence Shift Register (LSSR) shown in FIG. 2, and by other generator designs that are known in the art. For an N-stage LSSR, there are possibly 2N−1 bits (or “chips”) in the bit or data stream before the bit pattern of N bits within the stream must repeat. A similar q-phase polynomial exists; however, herein, only the i-phase will be discussed. The methods herein are equally applicable to q-phase signal correlation, or generally to any spectrum spread/despread communications system that uses a characteristic polynomial function or which can be represented by a characteristic polynomial.
A maximal length output stream exists where there are 2N−1 bits wherein each substring of N bits does not repeat. The substring of N consecutive bits of zeros is generally missing. However, U.S. Pat. Nos. 5,228,054 and 5,532,695 each teach a different method of creating an N-length substring of output bits of all zeros by inserting a zero into the substring of N−1 zeros bitstream. The insertion of the N-length all zeros substream of bits into the bitstream creates a PN generator capable of generating 2N bit patterns of length N. In non-maximal length PN generators, certain N-length substrings of the output bit stream will repeat within the periodic length of 2N−1 output bits.
Pseudorandom Noise number generators are typically used for creating an embedded reference signal that when decoded by the receiver, permits phase sequencing of the transmitted signal at the receiver, while at the same time such a signal can appear to other non-potential or non-targeted receivers as a ‘white noise’ background signal. In order to achieve signal correlation, the embedded pseudorandom reference signal is extracted from the received signal and compared to a pseudorandom signal generated by the receiver. Under certain circumstances, the pseudorandom sequence generated by the receiver must be advanced or delayed by more than one bit or symbol. In those instances where the pseudorandom sequence generated by the receiver must be advanced or delayed by more than a few bits (or a few symbols), it will be referred to herein as “jumping” and/or correlation to a future state or a non-sequential state.
In order to achieve phase sequencing or correlation between the transmitted and received signals, a future state or non-sequential state is determined by using the current phase sequence (or previously known present state) and a phase offset (or offset state) which may typically be provided as a fixed number of n bits or n symbols from the present state of the LSSR or a predetermined state. The desired future state of the LSSR can be determined by known conventional means such as retrieving the actual state from a memory array containing the actual states. Alternatively, the desired future state of the LSSR could also be computed by finding the value of the transition matrix P raised to the n-th power. Typically, for an N×N dimensioned transition matrix P it has here-to-date required N-product and (N−1)-addition steps for each of the N2 elements of the transition matrix P. In cellular phones using DSSS technology, the number of calculations necessary to compute most future states using the aforementioned computational methods (and similar computational methods) has typically prevented the use of such computational methods to directly compute or calculate a future state due to the range over which n will vary for matrices of size N. The number of calculations may be significantly large for larger values of N thereby making the here-to-date computational methods impractical or unsuitable for real time correlation for devices such as cellular phones.